# source: https://leetcode.cn/problems/shortest-subarray-to-be-removed-to-make-array-sorted/ 双指针 + 滑动窗口
class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        right = n - 1
        while right and arr[right - 1] <= arr[right]:
            right -= 1
        if right == 0:  # arr 已经是非递减数组
            return 0
        # 此时 arr[right-1] > arr[right]
        ans = right  # 删除 arr[:right]
        left = 0  # 枚举 left
        while left == 0 or arr[left - 1] <= arr[left]:
            while right < n and arr[right] < arr[left]:
                right += 1
            # 此时 arr[left] <= arr[right]，删除 arr[left+1:right]
            ans = min(ans, right - left - 1)
            left += 1
        return ans

# 法二: 二分查找 + 双指针
from typing import List
import bisect

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        
        # Step 1: Find the longest non-decreasing prefix
        left = 0
        while left + 1 < n and arr[left] <= arr[left + 1]:
            left += 1
        
        # If the whole array is already non-decreasing
        if left == n - 1:
            return 0
        
        # Step 2: Find the longest non-decreasing suffix
        right = n - 1
        while right > 0 and arr[right - 1] <= arr[right]:
            right -= 1
        
        # Step 3: Calculate the minimum length to remove
        # Case 1: Remove all middle elements between left and right
        result = min(n - left - 1, right)  # Either remove left or remove right
        
        # Case 2: Merge prefix and suffix using binary search
        for i in range(left + 1):
            pos = bisect.bisect_left(arr, arr[i], lo=right)
            if pos < n:
                result = min(result, pos - i - 1)
        
        return result

# source:https://leetcode.cn/problems/maximum-fruits-harvested-after-at-most-k-steps/description/ 
from typing import List

class Solution:
    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
        n = len(fruits)
        left, right = 0, 0
        total = 0
        max_fruits = 0

        while right < n:
            # 增加右边界的水果数量
            total += fruits[right][1]
            
            # 检查是否满足步数限制
            while left <= right:
                # 路径 1: 先向左，再向右
                left_to_right = abs(startPos - fruits[left][0]) + abs(fruits[right][0] - fruits[left][0])
                # 路径 2: 先向右，再向左
                right_to_left = abs(startPos - fruits[right][0]) + abs(fruits[right][0] - fruits[left][0])

                # 如果两种路径都超出步数限制，缩小窗口
                if min(left_to_right, right_to_left) > k:
                    total -= fruits[left][1]
                    left += 1
                else:
                    break

            # 更新最大水果数量
            max_fruits = max(max_fruits, total)
            right += 1

        return max_fruits
